package Graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class 出差 {
    static class Node {
        int val;
        long dist;
        List<Edge> bian;
        Boolean isFlag;
        int geli;

        public Node(int val) {
            this.val = val;
            dist = Long.MAX_VALUE;
            bian = new ArrayList<>();
            isFlag = false;
            geli = 0;
        }
    }

    static class Edge {
        long w;
        Node to;

        public Edge(Long w, Node to) {
            this.w = w;
            this.to = to;
        }
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int M = scanner.nextInt();
        Node[] nodes = new Node[N + 1];
        for (int i = 1; i <= N; i++) {
            nodes[i] = new Node(i);
            nodes[i].geli = scanner.nextInt();
        }

        for (int i = 1; i <= M; i++) {
            int from = scanner.nextInt(); // 起点城市编号
            int to = scanner.nextInt(); // 终点城市编号
            long time = scanner.nextInt(); // 经过该路线所需的时间
            nodes[from].bian.add(new Edge(time, nodes[to]));
            nodes[to].bian.add(new Edge(time, nodes[from])); // 假设路线是双向的
        }
        System.out.println(djs(nodes[1], nodes[N]));

    }

    public static long djs(Node start, Node end) {
        start.dist = 0;
        LinkedList<Node> linkedList = new LinkedList<>();
        linkedList.offer(start);
        while (!linkedList.isEmpty()) {
            Node poll = linkedList.poll();
            poll.isFlag = true;

            for (Edge edge : poll.bian) {
                Node nextNode = edge.to;
                if (!nextNode.isFlag) { // 如果邻居节点尚未访问过
                    long d = edge.w + nextNode.geli + poll.dist;
                    if (d < nextNode.dist) {
                        nextNode.dist = d;
                        linkedList.offer(nextNode);
                    }
                }
            }
        }
        return end.dist - end.geli;
    }
}
